力扣網站的說明
动态规划常常适用于有重叠子问题和最优子结构性质的问题，并且记录所有子问题的结果，因此动态规划方法所耗时间往往远少于朴素解法。
动态规划有自底向上和自顶向下两种解决问题的方式。自顶向下即记忆化递归，自底向上就是递推。
使用动态规划解决的问题有个明显的特点，一旦一个子问题的求解得到结果，以后的计算过程就不会修改它，这样的特点叫做无后效性，求解问题的过程形成了一张有向无环图。动态规划只解决每个子问题一次，具有天然剪枝的功能，从而减少计算量。

步驟可以整理成這樣
基礎狀態->寫出轉移方程（對狀態做推演）->變數的範圍&關係->程式碼

例題實戰

用一個最簡單的題目來應證步驟
70. 爬楼梯
1.基礎狀態
n = 1時答案是1
n = 2時答案是2
2.寫出轉移方程
經由題目可以發現每次只能上1or2階，所以第i階的方法數(dp[i])為dp[i-1]+dp[i-2]
dp[i] = dp[i-1]+dp[i-2]
3.變數的範圍
發現dp[i]需要dp[i-1]&dp[i-2]所以i需要由3~n

class Solution {
public:
    int climbStairs(int n) {
        if(n==1)
            return 1;
        if(n==2)
            return 2;
        vector<int> dp(n+1);
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i<=n; i++){
            dp[i] = dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
    //  遞迴法，超時
    // int climbStairs(int n) {
    //     if(n==1)
    //         return 1;
    //     if(n==2)
    //         return 2;
    //     return climbStairs(n-1)+climbStairs(n-2);
    // }
};

198. 打家劫舍
推演dp[i] = max(dp[i-1], dp[i-2]+nums[i])就結束了

class Solution {
public:

    //dp[i] = max(dp[i-1], dp[i-2]+nums[i])
    int rob(vector<int>& nums) {
        if(nums.size() == 0)
            return 0;
        if(nums.size() == 1)
        {
            return nums[0];
        }
        vector<int> dp(nums.size());
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        for(int i = 2; i < dp.size(); i++){
            dp[i] = max(dp[i-1], dp[i-2]+nums[i]);
        }
        return dp[dp.size()-1];
    }
};

121. 买卖股票的最佳时机
經典動態規劃問題，直接看程式碼

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //遍歷做法
        /*int Max = 0;
        for(int i = 0; i < prices.size(); i++)
        {
            for(int j = i; j < prices.size(); j++)
            {
                if(prices[j] - prices[i] > Max)
                {
                    Max = prices[j] - prices[i];
                }
            }
        }
        return Max;*/


        //DP思想  Max(上一個獲利組合, 現在賣出-最低價錢)
        /*if (prices.size()==0)
            return 0;
        int Max = 0, Min = prices[0];
        for(int i = 0; i<prices.size(); i++){
            Max = max(Max, prices[i]-Min);
            Min = min(Min, prices[i]);
        }
        return Max;*/

        //貪心想法
        int Max = 0;
        for(int i = 0, j = 0; j<prices.size(); j++){
            if(prices[j]-prices[i]>0){
                Max = max(Max, prices[j]-prices[i]);
            }
            else
                i = j;
        }
        return Max;
    }
};

補充一下貪心思路：
假設在第i天買入，今天是第j天＆prices[j]>prices[i]，能賺的價差就是prices[j]-prices[i]
若prices[j] < prices[i]，那就更新買入的時間點（i)，就可以保證最佳解